package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 * 784. 字母大小写全排列
 * https://leetcode.cn/problems/letter-case-permutation/description/
 * ```
 * 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
 * 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
 *
 * 示例 1：
 * 输入：s = "a1b2"
 * 输出：["a1b2", "a1B2", "A1b2", "A1B2"]
 * 示例 2:
 *
 * 输入: s = "3z4"
 * 输出: ["3z4","3Z4"]
 *
 * 提示:
 * 1 <= s.length <= 12
 * s 由小写英文字母、大写英文字母和数字组成
 * ```
 * 思路：![leetcode_784.jpg](../../../../images/leetcode_784.jpg)
 */
class leetcode_784 {
    @Test
    fun test_1() {
        val result = letterCasePermutation("a1b2")
        val expected = arrayListOf("a1b2", "A1b2", "A1B2", "a1B2")
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = letterCasePermutation("3z4")
        val expected = arrayListOf("3z4", "3Z4")
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_3() {
        val result = letterCasePermutation("C")
        val expected = arrayListOf("c", "C")
        Assert.assertEquals(expected, result)
    }

    /**
    回溯 - 全排列问题
    思路：
    2 字符串  -> 小写字符串 -> 字符数组
    3 遇到 小写字母  -> 大写字母
    4 回溯 （小写字母  -> 大写字母）
    5 收集结果时要去重
     */
    fun letterCasePermutation(s: String): List<String> {
        // TODO:lowercase
        f(s.lowercase().toCharArray(), 0)
        return result
    }

    var result: ArrayList<String> = ArrayList()

    fun f(s: CharArray, start: Int) {
        // 1 确定函数参数以及返回值
        // 2 确认终止条件
        // 收集结果
        val node = String(s)
        // 去重
        if (!result.contains(node)) {
            result.add(node)
        }
        // println("collect: result=$result")
        if (start == s.size) {
            return
        }

        // 3 确认循环遍历方向
        for (i in start until s.size) {
            // 也可以不判断，直接转成大写
//            if(s[i].isLetter()){
                // todo:uppercaseChar
                s[i] = s[i].uppercaseChar()
//            }

            // 递归
            f(s, i + 1)

            // 回溯
            // todo:lowercaseChar
            s[i] = s[i].lowercaseChar()

            // 4 剪枝？
            // 5 去重？
        }
    }
}